#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>


 void swp_order_it(std::vector<int> &v, std::vector<int> &tmp) {

    int sz = static_cast<int>(v.size() );


    // split interval
    // cal swp interval number
    int l = 0;
    int xlen = sz;


    for ( ; xlen > 2; xlen >>= 1) {
        std::copy(v.begin(), v.end(), tmp.begin());

        int cnt = sz / xlen;
        int lp = 0;
        int rp = xlen / 2;


        for (int i = 0;i < cnt; i++) {
            lp = i * xlen ;
            rp = i * xlen + xlen / 2;
            for (int j = 0;j < xlen; ++j) {
                if ( j & 1)
                    v[rp++] = tmp[i * xlen + j];
                else
                    v[lp++]   = tmp[i * xlen + j];
            }
        }
    }


}

 void swp_order(std::vector<int> &v, std::vector<int> &tmp,int l, int r) {
     if ( r - l <= 2)
         return ;
     int lp = l;
     int rp = (r + l) >> 1;
    

     for (int i = l;i < r;++i) {
         if ((i - l) & 1) {
             tmp[rp++] = v[i];
         }
         else {
             tmp[lp++] = v[i];
         }
     }

     std::copy( tmp.begin() + l, tmp.begin()  + r, v.begin() + l);

     swp_order( v, tmp, l, lp);
     swp_order( v, tmp, lp, rp);
 }

 int next_in_rev(int N, int k)
 {
    int ans = k;
    int diff = 1 << (N - 1);
    // 最高位置算

    // 找到最高的非1位置
    while (diff && ans >= diff ) {
        // 连续的高位1都需要减去
        ans -= diff;
        diff /= 2;
    }

    // 将它置为1
    ans += diff;

    return ans;
 }
 void print_bin(int nbits, int k) {
    for (int i = 0; i < nbits; ++i) {
        if (k & (1 << (nbits - 1 - i))) {
            printf("1");
        }
        else {
            printf("0");
        }
    }
    printf("\n");
}
void print_bin_rev(int NB_LEN) {
    int v = 0;
    for (int i = 0;i < (1 << NB_LEN); ++i) {
        print_bin(NB_LEN, v);
        v = next_in_rev(NB_LEN,v);
    }
}
void print_bin_rev2(int NB_LEN)
{
    int v = 0;
    for (int i = 0;i < (1 << NB_LEN); ++i) {
        print_bin(NB_LEN, v);
        int k = 1 << (NB_LEN - 1);
        while (k && v >= k) {
            v -= k;
            k >>= 1;
        }
        v += k;
    }
}


void swp_order_rev2(std::vector<int> &v)
{
    int sz = static_cast<int>(v.size());
    if ( sz <= 2)
        return;

    int msz = 2;
    while ( sz > msz)
        msz <<= 1;
    v.insert(v.end(), msz - sz, 0);
    std::iota(v.begin() + sz, v.end(), sz);

    // when we calculate R(x), we know R(0),R(1),...,R(x-1)
    // so we know R(x/2)
    // R(x) = R( x/2) >> 1 + (x & 1) * 2^(NB_LEN-1)


    std::vector<int> rev(msz, 0);
    for (int i = 1; i < msz; ++i) {
        int pos = rev[i >> 1] >> 1;
        if (i & 1)
            pos += (msz >> 1);
        rev[i] = pos;
    }
    for (int i = 1;i < msz; i++) {
        if (i < rev[i])
            std::swap(v[i], v[rev[i]]);
    }

}



void swp_order_rev(std::vector<int> &v) {


    int sz = static_cast<int>(v.size());
    if ( sz <= 2)
        return;

    int msz = 2;
    while ( sz > msz)
        msz <<= 1;
    v.insert(v.end(), msz - sz, 0);
    std::iota(v.begin() + sz, v.end(), sz);


    for (int i = 1, j = msz / 2,k;i < msz; ++i) {
        if (i < j) std::swap(v[i], v[j]);
        k = msz / 2;
        while (k && j >= k) {
            j -= k;
            k >>= 1;
        }
        j += k;
    }


}
void print_vec(const std::vector<int> &a)
{
    std::cout << "[";

    int sz = a.size();
    for (int i = 0;i < sz; ++i) {
        if (i) std::cout << ",";
        std::cout << a[i] ;
    }
    std::cout << "]" << std::endl;
}




int main(int argc, char *argv[])
{

    int N = 4;
    std::vector<int> a(10, 0);
    std::iota(a.begin(), a.end(), 0);
    print_vec(a);
    swp_order_rev2(a);
    print_vec(a);
    swp_order_rev2(a);
    print_vec(a);
    return 0;
}

